#ifndef __NONAME_LIST_H__
#define __NONAME_LIST_H__

#define NONAME_LIB_USE
#include <ntifs.h>
#include "nm_mem.h"

typedef BOOLEAN (__stdcall *COMPAREPROC)(PVOID Dst, PVOID Src);

template <class T>
struct _klist_entry {
	struct _klist_entry<T> *FLink, *BLink;
	T Value;
public:
	_klist_entry() {FLink = NULL; BLink = NULL;}
};

template <class T>
class klist {

public:

	BOOLEAN Insert(const T &Val, BOOLEAN InsertHead = TRUE);
	BOOLEAN Insert(const T &Val, const T &Refer, BOOLEAN InsertAfter);
	BOOLEAN Delete(const T &Val);
	void Destroy ();
public:

	ULONG Count() const { return m_Nodes; }
	T *First();
	T *Last();
	T *Next();
	T *Prev();
	T *operator[] (ULONG Index);
	BOOLEAN Exists(const T& Val);
	T* Find(const T& Val);
	T* Find(const T& Dst, COMPAREPROC CompareProc);
public:
	klist() : m_Nodes(0), m_ListHead(0), m_ListTail(0), m_CurNode(0) {};
	void Release() { Destroy (); }

private:
	typedef struct _klist_entry<T> KNODE;
	ULONG m_Nodes;
	KNODE *m_ListHead, *m_ListTail, *m_CurNode;
};


template <class T>
BOOLEAN klist<T>::Insert(const T &Val, BOOLEAN InsertHead /*= TRUE*/)
{
	KNODE *node;
	KNODE *p = m_ListHead;

	while (p != NULL) {
		if (p->Value == Val) {
			return TRUE;
		}
		p = p->FLink;
	}

	node = new KNODE;

	node->Value = Val;

	if (m_ListHead == NULL) {

		m_ListHead = m_ListTail = node;
		return TRUE;
	}

	if (InsertHead) {
		node->FLink = m_ListHead;
		node->FLink->BLink = node;
		m_ListHead = node;
	} 
	else {
		node->BLink = m_ListTail;
		node->BLink->FLink = node;
		m_ListTail = node;
	}

	m_Nodes++;
	return TRUE;
}

template <class T>
BOOLEAN klist<T>::Insert(const T &Val, const T &Refer, BOOLEAN InsertAfter)
{
	KNODE *node;
	KNODE *p = m_ListHead;
	while (p != NULL) {

		if (p->Value == Refer) {
			break;
		}
		p = p->FLink;
	}
	if (p == NULL) {
		return FALSE;
	}

	node = new KNODE;

	node->Value = Val;

	if (InsertAfter) {
		if (p == m_ListTail) {
			m_ListTail = node;
		}
		node->FLink = p->FLink;
		node->BLink = p;
		if (p->FLink != NULL) {
			p->FLink->BLink = node;
		}
		p->FLink = node;
	} 
	else {
		if (p == m_ListHead)
			m_ListHead = node;
		node->FLink = p;
		node->BLink = p->BLink;
		if (p->BLink != NULL) {
			p->BLink->FLink = node;
		}
		p->BLink = node;
	}

	m_Nodes++;
	return TRUE;
}

template <class T>
BOOLEAN klist<T>::Exists( const T& Val )
{
	KNODE* p = m_ListHead;
	while( p ) {
		if( p->Value == Val )
			return TRUE;
		p = p->FLink;
	}
	return FALSE;
}

template <class T>
T* klist<T>::Find( const T& Val )
{
	KNODE* p = m_ListHead;
	while(p != NULL) {
		if(p->Value == Val) {
			return &p->Value;
		}

		p = p->FLink;
	}
	return 0;
}

template <class T>
T* klist<T>::Find( const T& Dst, COMPAREPROC CompareProc )
{
	KNODE* p = m_ListHead;
	while(p != NULL) {
		if(CompareProc(&Dst, &p->Value)) {
			return &p->Value;
		}

		p = p->FLink;
	}
	return 0;
}

template <class T>
BOOLEAN klist<T>::Delete(const T &Val)
{
	KNODE *p = m_ListHead;

	while (p != NULL) {
		if (p->Value == Val) {
			break;
		}
		p = p->FLink;
	}
	if (p == NULL) {
		return FALSE;
	}

	if (p == m_CurNode) {
		m_CurNode = p->FLink;
	}

	if (p->FLink) {
		p->FLink->BLink = p->BLink;
	}
	if (p->BLink) {
		p->BLink->FLink = p->FLink;
	}
	if (p == m_ListHead) {
		m_ListHead = p->FLink;
	}
	if (p == m_ListTail) {
		m_ListTail = p->BLink;
	}

	delete p;
	m_Nodes--;
	return TRUE;
}

template <class T>
void klist<T>::Destroy()
{
	while (m_ListHead != NULL) {
		KNODE *p = m_ListHead;
		m_ListHead = p->FLink;
		delete p;
	}
	m_Nodes = 0;
	m_ListTail = NULL;
}

template <class T>
T* klist<T>::First()
{
	m_CurNode = m_ListHead;
	return m_ListHead != NULL ? &m_ListHead->Value : NULL;
}

template <class T>
T* klist<T>::Last()
{
	m_CurNode = m_ListTail;
	return m_ListTail != NULL ? &m_ListTail->Value : NULL;
}

template <class T>
T* klist<T>::Next()
{
	if (m_CurNode != NULL && m_CurNode->FLink != NULL) {
		m_CurNode = m_CurNode->FLink;
		return &m_CurNode->Value;
	}
	return NULL;
}

template <class T>
T* klist<T>::Prev()
{
	if (m_CurNode != NULL && m_CurNode->BLink != NULL) {
		m_CurNode = m_CurNode->BLink;
		return &m_CurNode->Value;
	}
	return NULL;
}

template <class T>
T* klist<T>::operator[] (ULONG Index)
{
	ULONG i;
	KNODE *p = m_ListHead;
	for (i = 0; p != NULL; i++) {
		if (i == Index) {
			return &p->Value;
		}
		p = p->FLink;
	}
	return NULL;
}


#endif

